/*
set Matrix zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
*/
#include <iostream>
#include <vector>
#include  <algorithm>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int> >& matrix) {
		int mSize = matrix.size();//row
		int eSize = matrix[0].size();//cloumn
		
		//vector<int> element(eSize,-1);
		//vector<vector<int> > result(mSize,element);
		vector<vector<int> > tempPixel;
		
		for(int i = 0; i < mSize; i++)
		{
			for(int j = 0; j < eSize; j++)
			{
				if(matrix[i][j] == 0)
				{
					vector<int> temp;
					temp.push_back(i);
					temp.push_back(j);
					tempPixel.push_back(temp);
				}
				
			}
		}
		
		for(int i = 0; i < tempPixel.size(); i++)
		{
			for(int row = 0; row < mSize; row++ )
				matrix[row][tempPixel[i][1]] = 0;
			for(int col = 0; col < eSize; col++ )
				matrix[tempPixel[i][0]][col] = 0;
		}
		
		
    }
};
int main()
{
	cout<<"Set Matrix Zeros"<<endl;
	int a1[] = {1,2,3};
	int a2[] = {4,0,6};
	int a3[] = {7,8,9};
	vector<vector<int> > matrix;
	vector<int> element1(a1, a1 + sizeof(a1)/sizeof(int));
	vector<int> element2(a2, a2 + sizeof(a2)/sizeof(int));
	vector<int> element3(a3, a3 + sizeof(a3)/sizeof(int));
	
	matrix.push_back(element1);
	matrix.push_back(element2);
	matrix.push_back(element3);
	
	cout<<"size: " << matrix.size()<<endl;
	
	Solution s;
	s.setZeroes(matrix);
	cout<<"After...."<<endl;
	
	for(int i = 0; i < matrix.size(); i++)
	{
		for(int j = 0; j < matrix[1].size(); j++)
		{
			cout<<matrix[i][j]<<" ";
				
		}
		cout<<endl;
	}
	
	
	return 0;
}